package me.zk;

import java.util.Arrays;

/**
 * @Author: zhang kai
 * @Date: 2022/06/29
 * @Description:
 */
public class HeapSortDemo {

    public static void downAdjust(int[] array,int parentIndex,int length) {
        int tmp = array[parentIndex];
        int childIndex = 2 * parentIndex +1;
        while (childIndex < length) {
            if(childIndex +1 < length && array[childIndex+1] > array[childIndex]) {
                childIndex++;
            }
            if (tmp >= array[childIndex]){
                break;
            }
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * childIndex +1;
        }
        array[parentIndex] = tmp;
    }
    public static void heapSort(int[] array){
        for (int i= (array.length-2)/2;i>0;i--){
            downAdjust(array,i,array.length);
        }
        System.out.println(Arrays.toString(array));
        for (int i = array.length-1; i>0; i--) {
            int tmp = array[i];
            array[i] = array[0];
            array[0]=tmp;
            downAdjust(array,0,i);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,3,2,6,5,7,8,9,10,0};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
